package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/9 16:56
 */
public class M0410 {

    /** https://leetcode-cn.com/problems/check-subtree-lcci/ */
    public static boolean checkSubTree(TreeNode t1, TreeNode t2) {
        if(t2 == null) return true;
        if(t1 == null) return false;
        return isEqual(t1, t2) || checkSubTree(t1.left, t2) || checkSubTree(t1.right, t2);
    }

    public static boolean isEqual(TreeNode t1, TreeNode t2) {
        if (t1 == t2) return true;
        if (t1 == null || t2 == null) return false;
        return t1.val == t2.val && isEqual(t1.left, t2.left) && isEqual(t1.right, t2.right);
    }

    public static boolean checkSubTree2(TreeNode t1, TreeNode t2) {
        t1 = traversal(t1, t2.val);
        return check(t1, t2);
    }

    public static boolean check(TreeNode p1, TreeNode p2) {
        if (p1 == null && p2 != null)
            return false;
        if (p1 != null && p2 == null)
            return false;
        if (p1 == null && p2 == null)
            return true;
        return p1.val == p2.val;
    }

    public static TreeNode traversal(TreeNode t1, int value) {
        if (t1 == null)
            return null;
        if (t1.val == value)
            return t1;
        TreeNode result = null;
        if (t1.left != null) {
            result = traversal(t1.left, value);
            if (result != null)
                return result;
        }

        if (t1.right != null)
            result = traversal(t1.right, value);
        return result;
    }

}
